<!DOCTYPE html>
<html lang="zh-Hans">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <meta http-equiv="X-UA-Compatible" content="ie=edge" />
    <title>
C语言基础知识(五)
</title>

    


  
  <meta name="author" content="zhitaoZ" />
  <meta name="description" content="No one is a island" />



<meta name="generator" content="Hugo 0.65.3" />

<link rel="canonical" href="https://zhitaoz.github.io/post/learnc5/" />


<meta property="og:title" content="C语言基础知识(五)" />
<meta property="og:description" content="C语言基础知识 (五)" />
<meta property="og:type" content="article" />
<meta property="og:url" content="https://zhitaoz.github.io/post/learnc5/" />
<meta property="article:published_time" content="2020-03-13T14:29:13+08:00" />
<meta property="article:modified_time" content="2020-03-13T17:30:45+08:00" />



<meta name="twitter:card" content="summary"/>
<meta name="twitter:title" content="C语言基础知识(五)"/>
<meta name="twitter:description" content="C语言基础知识 (五)"/>


<link rel="stylesheet" href="/css/github-markdown.css" />
<link rel="stylesheet" href="/css/semantic.min.css" />
<link rel="stylesheet" href="/css/site.css" />


<style>
  a {
    color: seagreen !important;
  }
</style>



<style>
  .inverted a {
     color: darkseagreen !important;
  }
</style>


  </head>

  
  <body style="background-image: url(/me/background.jpg);">
  
    <div class="flip-container">
      <div class="flipper">
        <section class="front">
          
<nav class="ui secondary inverted menu dream-menu">

  <div class="item">
    <i class="large link bullseye icon dream-flip-toggle" title="Flip it!"></i>
  </div>
  <div class="item">
    <i class="large link home icon" title="Home" onclick="window.location.href = 'https:\/\/zhitaoz.github.io\/'"></i>
  </div>
  <div class="item">
    <i id="theme-switch" class="large link icon" onclick="themeSwitch()"></i>
  </div>
</nav>

          
<div class="ui centered relaxed grid dream-grid">
  <div class="sixteen wide mobile sixteen wide tablet twelve wide computer column markdown-body dream-single">

    <section class="ui top attached segment" id="dream-save-post-as-img">
      <header style="margin-top: 0 !important;">
        <h2 class="ui header">
          C语言基础知识(五)
          <div class="sub header">@ zhitaoZ · Friday, Mar 13, 2020 · 6 minute read · Update at Mar 13, 2020</div>
        </h2>
      </header>
      <article style="margin-top: 2rem;"><p>C语言基础知识 (五)</p>
<h2 id="二十六c强制类型转换">二十六、C强制类型转换</h2>
<p>强制类型转换是把变量从一种类型转换为另一种数据类型。<br>
类型转换可以是隐式的，由编译器自动执行，也可以是显式的，通过使用强制类型转换运算符来指定。在编程时，有需要类型转换的时候都用上强制类型转换运算符，是一种良好的编程习惯。</p>
<h3 id="整数提升">整数提升</h3>
<p>整数提升是指把小于 int 或 unsigned int 的整数类型转换为 int 或 unsigned int 的过程</p>
<h3 id="常用的算术转换">常用的算术转换</h3>
<p>常用的算术转换是隐式地把值强制转换为相同的类型。编译器首先执行整数提升，如果操作数类型不同，则它们会被转换为下列层次中出现的最高层次的类型：<br>
<img src="/img/usual_arithmetic_conversion.png" alt="转换顺序"></p>
<p>常用的算术转换不适用于赋值运算符、逻辑运算符 &amp;&amp; 和 ||。</p>
<h2 id="二十七c错误处理">二十七、C错误处理</h2>
<p>C 语言不提供对错误处理的直接支持，但是作为一种系统编程语言，它以返回值的形式允许您访问底层数据。在发生错误时，大多数的 C 或 UNIX 函数调用返回 1 或 NULL，同时会设置一个错误代码 errno，该错误代码是全局变量，表示在函数调用期间发生了错误。可以在 errno.h 头文件中找到各种各样的错误代码。<br>
所以，C 程序员可以通过检查返回值，然后根据返回值决定采取哪种适当的动作。开发人员应该在程序初始化时，把 errno 设置为 0，这是一种良好的编程习惯。0 值表示程序中没有错误。</p>
<h3 id="errnoperror-和-strerror">errno、perror() 和 strerror()</h3>
<p>C 语言提供了 perror() 和 strerror() 函数来显示与 errno 相关的文本消息。</p>
<ul>
<li>perror() 函数显示您传给它的字符串，后跟一个冒号、一个空格和当前 errno 值的文本表示形式。</li>
<li>strerror() 函数，返回一个指针，指针指向当前 errno 值的文本表示形式。</li>
</ul>
<h3 id="除数为零的错误">除数为零的错误</h3>
<p>在进行除法运算时，如果不检查除数是否为零，则会导致一个运行时错误。</p>
<h3 id="程序退出状态">程序退出状态</h3>
<p>通常情况下，程序成功执行完一个操作正常退出的时候会带有值 EXIT_SUCCESS。在这里，EXIT_SUCCESS 是宏，它被定义为 0。<br>
如果程序中存在一种错误情况，当您退出程序时，会带有状态值 EXIT_FAILURE，被定义为 -1。</p>
<h2 id="二十八c递归">二十八、C递归</h2>
<p>递归指的是在函数的定义中使用函数自身的方法。<br>
C 语言支持递归，即一个函数可以调用其自身。但在使用递归时，程序员需要注意定义一个从函数退出的条件，否则会进入死循环。<br>
递归函数在解决许多数学问题上起了至关重要的作用，比如计算一个数的阶乘、生成斐波那契数列，等等。</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-c" data-lang="c"><span style="color:#66d9ef">void</span> <span style="color:#a6e22e">recursion</span>()
{
   statements;
   ... ... ...
   recursion(); <span style="color:#75715e">/* 函数调用自身 */</span>
   ... ... ...
}

<span style="color:#66d9ef">int</span> <span style="color:#a6e22e">main</span>()
{
   recursion();
}
</code></pre></div><h2 id="二十九c可变参数命令行参数">二十九、C可变参数\命令行参数</h2>
<h3 id="可变参数">可变参数</h3>
<p>使用 stdarg.h 头文件，该文件提供了实现可变参数功能的函数和宏。具体步骤如下：</p>
<ul>
<li>定义一个函数，最后一个参数为省略号，省略号前面可以设置自定义参数。</li>
<li>在函数定义中创建一个 va_list 类型变量，该类型是在 stdarg.h 头文件中定义的。</li>
<li>使用 int 参数和 va_start 宏来初始化 va_list 变量为一个参数列表。宏 va_start 是在 stdarg.h 头文件中定义的。</li>
<li>使用 va_arg 宏和 va_list 变量来访问参数列表中的每个项。</li>
<li>使用宏 va_end 来清理赋予 va_list 变量的内存。</li>
</ul>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-c" data-lang="c"><span style="color:#75715e">#include</span> <span style="color:#75715e">&lt;stdio.h&gt;</span><span style="color:#75715e">
</span><span style="color:#75715e">#include</span> <span style="color:#75715e">&lt;stdarg.h&gt;</span><span style="color:#75715e">
</span><span style="color:#75715e"></span>
<span style="color:#66d9ef">double</span> <span style="color:#a6e22e">average</span>(<span style="color:#66d9ef">int</span> num,...)
{

    va_list valist;
    <span style="color:#66d9ef">double</span> sum <span style="color:#f92672">=</span> <span style="color:#ae81ff">0.0</span>;
    <span style="color:#66d9ef">int</span> i;

    <span style="color:#75715e">/* 为 num 个参数初始化 valist */</span>
    va_start(valist, num);

    <span style="color:#75715e">/* 访问所有赋给 valist 的参数 */</span>
    <span style="color:#66d9ef">for</span> (i <span style="color:#f92672">=</span> <span style="color:#ae81ff">0</span>; i <span style="color:#f92672">&lt;</span> num; i<span style="color:#f92672">++</span>)
    {
       sum <span style="color:#f92672">+=</span> va_arg(valist, <span style="color:#66d9ef">int</span>);
    }
    <span style="color:#75715e">/* 清理为 valist 保留的内存 */</span>
    va_end(valist);

    <span style="color:#66d9ef">return</span> sum<span style="color:#f92672">/</span>num;
}

<span style="color:#66d9ef">int</span> <span style="color:#a6e22e">main</span>()
{
   printf(<span style="color:#e6db74">&#34;Average of 2, 3, 4, 5 = %f</span><span style="color:#ae81ff">\n</span><span style="color:#e6db74">&#34;</span>, average(<span style="color:#ae81ff">4</span>, <span style="color:#ae81ff">2</span>,<span style="color:#ae81ff">3</span>,<span style="color:#ae81ff">4</span>,<span style="color:#ae81ff">5</span>));
   printf(<span style="color:#e6db74">&#34;Average of 5, 10, 15 = %f</span><span style="color:#ae81ff">\n</span><span style="color:#e6db74">&#34;</span>, average(<span style="color:#ae81ff">3</span>, <span style="color:#ae81ff">5</span>,<span style="color:#ae81ff">10</span>,<span style="color:#ae81ff">15</span>));
}
</code></pre></div><h2 id="命令行参数">命令行参数</h2>
<p>执行程序时，可以从命令行传值给 C 程序。这些值被称为命令行参数，它们对程序很重要，特别是想从外部控制程序，而不是在代码内对这些值进行硬编码时，就显得尤为重要了。<br>
命令行参数是使用 main() 函数参数来处理的，其中，argc 是指传入参数的个数，argv[] 是一个指针数组，指向传递给程序的每个参数。</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-c" data-lang="c"><span style="color:#75715e">#include</span> <span style="color:#75715e">&lt;stdio.h&gt;</span><span style="color:#75715e">
</span><span style="color:#75715e"></span>
<span style="color:#66d9ef">int</span> <span style="color:#a6e22e">main</span>( <span style="color:#66d9ef">int</span> argc, <span style="color:#66d9ef">char</span> <span style="color:#f92672">*</span>argv[] )  
{
   <span style="color:#66d9ef">if</span>( argc <span style="color:#f92672">==</span> <span style="color:#ae81ff">2</span> )
   {
      printf(<span style="color:#e6db74">&#34;The argument supplied is %s</span><span style="color:#ae81ff">\n</span><span style="color:#e6db74">&#34;</span>, argv[<span style="color:#ae81ff">1</span>]);
   }
   <span style="color:#66d9ef">else</span> <span style="color:#66d9ef">if</span>( argc <span style="color:#f92672">&gt;</span> <span style="color:#ae81ff">2</span> )
   {
      printf(<span style="color:#e6db74">&#34;Too many arguments supplied.</span><span style="color:#ae81ff">\n</span><span style="color:#e6db74">&#34;</span>);
   }
   <span style="color:#66d9ef">else</span>
   {
      printf(<span style="color:#e6db74">&#34;One argument expected.</span><span style="color:#ae81ff">\n</span><span style="color:#e6db74">&#34;</span>);
   }
}
</code></pre></div><p>argv[0] 存储程序的名称，argv[1] 是一个指向第一个命令行参数的指针，*argv[n] 是最后一个参数。如果没有提供任何参数，argc 将为 1，否则，如果传递了一个参数，argc 将被设置为 2。<br>
多个命令行参数之间用空格分隔，但是如果参数本身带有空格，那么传递参数的时候应把参数放置在双引号 &quot;&rdquo; 或单引号 '&rsquo; 内部。</p>
<h2 id="三十c内存管理">三十、C内存管理</h2>
<p>C 语言为内存的分配和管理提供了几个函数。这些函数可以在 &lt;stdlib.h&gt; 头文件中找到。</p>
<table>
<thead>
<tr>
<th>函数</th>
<th>描述</th>
</tr>
</thead>
<tbody>
<tr>
<td>void *calloc(int num, int size);</td>
<td>在内存中动态地分配 num 个长度为 size 的连续空间，并将每一个字节都初始化为 0。所以它的结果是分配了 num*size 个字节长度的内存空间，并且每个字节的值都是0。</td>
</tr>
<tr>
<td>void free(void *address);</td>
<td>该函数释放 address 所指向的内存块,释放的是动态分配的内存空间。</td>
</tr>
<tr>
<td>void *malloc(int num);</td>
<td>在堆区分配一块指定大小的内存空间，用来存放数据。这块内存空间在函数执行完成后不会被初始化，它们的值是未知的。</td>
</tr>
<tr>
<td>void *realloc(void *address, int newsize);</td>
<td>该函数重新分配内存，把内存扩展到 newsize。</td>
</tr>
</tbody>
</table>
<p><strong>注意</strong>：void * 类型表示未确定类型的指针。C、C++ 规定 void * 类型可以通过类型转换强制转换为任何其它类型的指针。</p>
<h3 id="动态分配内存">动态分配内存</h3>
<p>编程时，如果您预先知道数组的大小，那么定义数组时就比较容易。例如，一个存储人名的数组，它最多容纳 100 个字符，所以您可以定义数组，如下所示：</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-c" data-lang="c"><span style="color:#66d9ef">char</span> name[<span style="color:#ae81ff">100</span>];
</code></pre></div><p>但是，如果您预先不知道需要存储的文本长度，我们需要定义一个指针，该指针指向未定义所需内存大小的字符，后续再根据需求来分配内存。<br>
当动态分配内存时，您有完全控制权，可以传递任何大小的值。而那些预先定义了大小的数组，一旦定义则无法改变大小。</p>
<p>###重新调整内存的大小和释放内存</p>
<p>当程序退出时，操作系统会自动释放所有分配给程序的内存，但是，建议您在不需要内存时，都应该调用函数 free() 来释放内存。或者可以通过调用函数 realloc() 来增加或减少已分配的内存块的大小。</p>
<h2 id="c排序算法">C排序算法</h2>
<ul>
<li>冒泡排序</li>
</ul>
<p>冒泡排序（英语：Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-c" data-lang="c"><span style="color:#75715e">#include</span> <span style="color:#75715e">&lt;stdio.h&gt;</span><span style="color:#75715e">
</span><span style="color:#75715e"></span><span style="color:#66d9ef">void</span> <span style="color:#a6e22e">bubble_sort</span>(<span style="color:#66d9ef">int</span> arr[], <span style="color:#66d9ef">int</span> len) {
    <span style="color:#66d9ef">int</span> i, j, temp;
    <span style="color:#66d9ef">for</span> (i <span style="color:#f92672">=</span> <span style="color:#ae81ff">0</span>; i <span style="color:#f92672">&lt;</span> len <span style="color:#f92672">-</span> <span style="color:#ae81ff">1</span>; i<span style="color:#f92672">++</span>)
        <span style="color:#66d9ef">for</span> (j <span style="color:#f92672">=</span> <span style="color:#ae81ff">0</span>; j <span style="color:#f92672">&lt;</span> len <span style="color:#f92672">-</span> <span style="color:#ae81ff">1</span> <span style="color:#f92672">-</span> i; j<span style="color:#f92672">++</span>)
            <span style="color:#66d9ef">if</span> (arr[j] <span style="color:#f92672">&gt;</span> arr[j <span style="color:#f92672">+</span> <span style="color:#ae81ff">1</span>]) {
                temp <span style="color:#f92672">=</span> arr[j];
                arr[j] <span style="color:#f92672">=</span> arr[j <span style="color:#f92672">+</span> <span style="color:#ae81ff">1</span>];
                arr[j <span style="color:#f92672">+</span> <span style="color:#ae81ff">1</span>] <span style="color:#f92672">=</span> temp;
            }
}
<span style="color:#66d9ef">int</span> <span style="color:#a6e22e">main</span>() {
    <span style="color:#66d9ef">int</span> arr[] <span style="color:#f92672">=</span> { <span style="color:#ae81ff">22</span>, <span style="color:#ae81ff">34</span>, <span style="color:#ae81ff">3</span>, <span style="color:#ae81ff">32</span>, <span style="color:#ae81ff">82</span>, <span style="color:#ae81ff">55</span>, <span style="color:#ae81ff">89</span>, <span style="color:#ae81ff">50</span>, <span style="color:#ae81ff">37</span>, <span style="color:#ae81ff">5</span>, <span style="color:#ae81ff">64</span>, <span style="color:#ae81ff">35</span>, <span style="color:#ae81ff">9</span>, <span style="color:#ae81ff">70</span> };
    <span style="color:#66d9ef">int</span> len <span style="color:#f92672">=</span> (<span style="color:#66d9ef">int</span>) <span style="color:#66d9ef">sizeof</span>(arr) <span style="color:#f92672">/</span> <span style="color:#66d9ef">sizeof</span>(<span style="color:#f92672">*</span>arr);
    bubble_sort(arr, len);
    <span style="color:#66d9ef">int</span> i;
    <span style="color:#66d9ef">for</span> (i <span style="color:#f92672">=</span> <span style="color:#ae81ff">0</span>; i <span style="color:#f92672">&lt;</span> len; i<span style="color:#f92672">++</span>)
        printf(<span style="color:#e6db74">&#34;%d &#34;</span>, arr[i]);
    <span style="color:#66d9ef">return</span> <span style="color:#ae81ff">0</span>;
}
</code></pre></div><ul>
<li>选择排序</li>
</ul>
<p>选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-c" data-lang="c"><span style="color:#66d9ef">void</span> <span style="color:#a6e22e">swap</span>(<span style="color:#66d9ef">int</span> <span style="color:#f92672">*</span>a,<span style="color:#66d9ef">int</span> <span style="color:#f92672">*</span>b) <span style="color:#75715e">//交換兩個變數
</span><span style="color:#75715e"></span>{
    <span style="color:#66d9ef">int</span> temp <span style="color:#f92672">=</span> <span style="color:#f92672">*</span>a;
    <span style="color:#f92672">*</span>a <span style="color:#f92672">=</span> <span style="color:#f92672">*</span>b;
    <span style="color:#f92672">*</span>b <span style="color:#f92672">=</span> temp;
}
<span style="color:#66d9ef">void</span> <span style="color:#a6e22e">selection_sort</span>(<span style="color:#66d9ef">int</span> arr[], <span style="color:#66d9ef">int</span> len) 
{
    <span style="color:#66d9ef">int</span> i,j;

    <span style="color:#66d9ef">for</span> (i <span style="color:#f92672">=</span> <span style="color:#ae81ff">0</span> ; i <span style="color:#f92672">&lt;</span> len <span style="color:#f92672">-</span> <span style="color:#ae81ff">1</span> ; i<span style="color:#f92672">++</span>) 
    {
        <span style="color:#66d9ef">int</span> min <span style="color:#f92672">=</span> i;
        <span style="color:#66d9ef">for</span> (j <span style="color:#f92672">=</span> i <span style="color:#f92672">+</span> <span style="color:#ae81ff">1</span>; j <span style="color:#f92672">&lt;</span> len; j<span style="color:#f92672">++</span>)     <span style="color:#75715e">//走訪未排序的元素
</span><span style="color:#75715e"></span>            <span style="color:#66d9ef">if</span> (arr[j] <span style="color:#f92672">&lt;</span> arr[min])    <span style="color:#75715e">//找到目前最小值
</span><span style="color:#75715e"></span>                min <span style="color:#f92672">=</span> j;    <span style="color:#75715e">//紀錄最小值
</span><span style="color:#75715e"></span>           swap(<span style="color:#f92672">&amp;</span>arr[min], <span style="color:#f92672">&amp;</span>arr[i]);    <span style="color:#75715e">//做交換
</span><span style="color:#75715e"></span>    }
}
</code></pre></div><ul>
<li>插入排序</li>
</ul>
<p>插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-c" data-lang="c"><span style="color:#66d9ef">void</span> <span style="color:#a6e22e">insertion_sort</span>(<span style="color:#66d9ef">int</span> arr[], <span style="color:#66d9ef">int</span> len){
    <span style="color:#66d9ef">int</span> i,j,temp;
    <span style="color:#66d9ef">for</span> (i<span style="color:#f92672">=</span><span style="color:#ae81ff">1</span>;i<span style="color:#f92672">&lt;</span>len;i<span style="color:#f92672">++</span>){
            temp <span style="color:#f92672">=</span> arr[i];
            <span style="color:#66d9ef">for</span> (j<span style="color:#f92672">=</span>i;j<span style="color:#f92672">&gt;</span><span style="color:#ae81ff">0</span> <span style="color:#f92672">&amp;&amp;</span> arr[j<span style="color:#f92672">-</span><span style="color:#ae81ff">1</span>]<span style="color:#f92672">&gt;</span>temp;j<span style="color:#f92672">--</span>)
                    arr[j] <span style="color:#f92672">=</span> arr[j<span style="color:#f92672">-</span><span style="color:#ae81ff">1</span>];
            arr[j] <span style="color:#f92672">=</span> temp;
    }
}
</code></pre></div><ul>
<li>希尔排序</li>
</ul>
<p>希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。<br>
希尔排序是基于插入排序的以下两点性质而提出改进方法的：</p>
<ol>
<li>插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率</li>
<li>但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位</li>
</ol>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-c" data-lang="c"><span style="color:#66d9ef">void</span> <span style="color:#a6e22e">shell_sort</span>(<span style="color:#66d9ef">int</span> arr[], <span style="color:#66d9ef">int</span> len) {
    <span style="color:#66d9ef">int</span> gap, i, j;
    <span style="color:#66d9ef">int</span> temp;
    <span style="color:#66d9ef">for</span> (gap <span style="color:#f92672">=</span> len <span style="color:#f92672">&gt;&gt;</span> <span style="color:#ae81ff">1</span>; gap <span style="color:#f92672">&gt;</span> <span style="color:#ae81ff">0</span>; gap <span style="color:#f92672">=</span> gap <span style="color:#f92672">&gt;&gt;</span> <span style="color:#ae81ff">1</span>)
        <span style="color:#66d9ef">for</span> (i <span style="color:#f92672">=</span> gap; i <span style="color:#f92672">&lt;</span> len; i<span style="color:#f92672">++</span>) {
            temp <span style="color:#f92672">=</span> arr[i];
            <span style="color:#66d9ef">for</span> (j <span style="color:#f92672">=</span> i <span style="color:#f92672">-</span> gap; j <span style="color:#f92672">&gt;=</span> <span style="color:#ae81ff">0</span> <span style="color:#f92672">&amp;&amp;</span> arr[j] <span style="color:#f92672">&gt;</span> temp; j <span style="color:#f92672">-=</span> gap)
                arr[j <span style="color:#f92672">+</span> gap] <span style="color:#f92672">=</span> arr[j];
            arr[j <span style="color:#f92672">+</span> gap] <span style="color:#f92672">=</span> temp;
        }
}
</code></pre></div><ul>
<li>归并排序</li>
</ul>
<p>把数据分为两段，从两段中逐个选最小的元素移入新数据段的末尾。
可从上到下或从下到上进行。</p>
<p><em><strong>迭代法</strong></em></p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-c" data-lang="c"><span style="color:#66d9ef">int</span> <span style="color:#a6e22e">min</span>(<span style="color:#66d9ef">int</span> x, <span style="color:#66d9ef">int</span> y) {
    <span style="color:#66d9ef">return</span> x <span style="color:#f92672">&lt;</span> y <span style="color:#f92672">?</span> x : y;
}
<span style="color:#66d9ef">void</span> <span style="color:#a6e22e">merge_sort</span>(<span style="color:#66d9ef">int</span> arr[], <span style="color:#66d9ef">int</span> len) {
    <span style="color:#66d9ef">int</span><span style="color:#f92672">*</span> a <span style="color:#f92672">=</span> arr;
    <span style="color:#66d9ef">int</span><span style="color:#f92672">*</span> b <span style="color:#f92672">=</span> (<span style="color:#66d9ef">int</span><span style="color:#f92672">*</span>) malloc(len <span style="color:#f92672">*</span> <span style="color:#66d9ef">sizeof</span>(<span style="color:#66d9ef">int</span>));
    <span style="color:#66d9ef">int</span> seg, start;
    <span style="color:#66d9ef">for</span> (seg <span style="color:#f92672">=</span> <span style="color:#ae81ff">1</span>; seg <span style="color:#f92672">&lt;</span> len; seg <span style="color:#f92672">+=</span> seg) {
        <span style="color:#66d9ef">for</span> (start <span style="color:#f92672">=</span> <span style="color:#ae81ff">0</span>; start <span style="color:#f92672">&lt;</span> len; start <span style="color:#f92672">+=</span> seg <span style="color:#f92672">+</span> seg) {
            <span style="color:#66d9ef">int</span> low <span style="color:#f92672">=</span> start, mid <span style="color:#f92672">=</span> min(start <span style="color:#f92672">+</span> seg, len), high <span style="color:#f92672">=</span> min(start <span style="color:#f92672">+</span> seg <span style="color:#f92672">+</span> seg, len);
            <span style="color:#66d9ef">int</span> k <span style="color:#f92672">=</span> low;
            <span style="color:#66d9ef">int</span> start1 <span style="color:#f92672">=</span> low, end1 <span style="color:#f92672">=</span> mid;
            <span style="color:#66d9ef">int</span> start2 <span style="color:#f92672">=</span> mid, end2 <span style="color:#f92672">=</span> high;
            <span style="color:#66d9ef">while</span> (start1 <span style="color:#f92672">&lt;</span> end1 <span style="color:#f92672">&amp;&amp;</span> start2 <span style="color:#f92672">&lt;</span> end2)
                b[k<span style="color:#f92672">++</span>] <span style="color:#f92672">=</span> a[start1] <span style="color:#f92672">&lt;</span> a[start2] <span style="color:#f92672">?</span> a[start1<span style="color:#f92672">++</span>] <span style="color:#f92672">:</span> a[start2<span style="color:#f92672">++</span>];
            <span style="color:#66d9ef">while</span> (start1 <span style="color:#f92672">&lt;</span> end1)
                b[k<span style="color:#f92672">++</span>] <span style="color:#f92672">=</span> a[start1<span style="color:#f92672">++</span>];
            <span style="color:#66d9ef">while</span> (start2 <span style="color:#f92672">&lt;</span> end2)
                b[k<span style="color:#f92672">++</span>] <span style="color:#f92672">=</span> a[start2<span style="color:#f92672">++</span>];
        }
        <span style="color:#66d9ef">int</span><span style="color:#f92672">*</span> temp <span style="color:#f92672">=</span> a;
        a <span style="color:#f92672">=</span> b;
        b <span style="color:#f92672">=</span> temp;
    }
    <span style="color:#66d9ef">if</span> (a <span style="color:#f92672">!=</span> arr) {
        <span style="color:#66d9ef">int</span> i;
        <span style="color:#66d9ef">for</span> (i <span style="color:#f92672">=</span> <span style="color:#ae81ff">0</span>; i <span style="color:#f92672">&lt;</span> len; i<span style="color:#f92672">++</span>)
            b[i] <span style="color:#f92672">=</span> a[i];
        b <span style="color:#f92672">=</span> a;
    }
    free(b);
}
</code></pre></div><p><em><strong>递归法</strong></em></p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-c" data-lang="c"><span style="color:#66d9ef">void</span> <span style="color:#a6e22e">merge_sort_recursive</span>(<span style="color:#66d9ef">int</span> arr[], <span style="color:#66d9ef">int</span> reg[], <span style="color:#66d9ef">int</span> start, <span style="color:#66d9ef">int</span> end) {
    <span style="color:#66d9ef">if</span> (start <span style="color:#f92672">&gt;=</span> end)
        <span style="color:#66d9ef">return</span>;
    <span style="color:#66d9ef">int</span> len <span style="color:#f92672">=</span> end <span style="color:#f92672">-</span> start, mid <span style="color:#f92672">=</span> (len <span style="color:#f92672">&gt;&gt;</span> <span style="color:#ae81ff">1</span>) <span style="color:#f92672">+</span> start;
    <span style="color:#66d9ef">int</span> start1 <span style="color:#f92672">=</span> start, end1 <span style="color:#f92672">=</span> mid;
    <span style="color:#66d9ef">int</span> start2 <span style="color:#f92672">=</span> mid <span style="color:#f92672">+</span> <span style="color:#ae81ff">1</span>, end2 <span style="color:#f92672">=</span> end;
    merge_sort_recursive(arr, reg, start1, end1);
    merge_sort_recursive(arr, reg, start2, end2);
    <span style="color:#66d9ef">int</span> k <span style="color:#f92672">=</span> start;
    <span style="color:#66d9ef">while</span> (start1 <span style="color:#f92672">&lt;=</span> end1 <span style="color:#f92672">&amp;&amp;</span> start2 <span style="color:#f92672">&lt;=</span> end2)
        reg[k<span style="color:#f92672">++</span>] <span style="color:#f92672">=</span> arr[start1] <span style="color:#f92672">&lt;</span> arr[start2] <span style="color:#f92672">?</span> arr[start1<span style="color:#f92672">++</span>] <span style="color:#f92672">:</span> arr[start2<span style="color:#f92672">++</span>];
    <span style="color:#66d9ef">while</span> (start1 <span style="color:#f92672">&lt;=</span> end1)
        reg[k<span style="color:#f92672">++</span>] <span style="color:#f92672">=</span> arr[start1<span style="color:#f92672">++</span>];
    <span style="color:#66d9ef">while</span> (start2 <span style="color:#f92672">&lt;=</span> end2)
        reg[k<span style="color:#f92672">++</span>] <span style="color:#f92672">=</span> arr[start2<span style="color:#f92672">++</span>];
    <span style="color:#66d9ef">for</span> (k <span style="color:#f92672">=</span> start; k <span style="color:#f92672">&lt;=</span> end; k<span style="color:#f92672">++</span>)
        arr[k] <span style="color:#f92672">=</span> reg[k];
}
<span style="color:#66d9ef">void</span> <span style="color:#a6e22e">merge_sort</span>(<span style="color:#66d9ef">int</span> arr[], <span style="color:#66d9ef">const</span> <span style="color:#66d9ef">int</span> len) {
    <span style="color:#66d9ef">int</span> reg[len];
    merge_sort_recursive(arr, reg, <span style="color:#ae81ff">0</span>, len <span style="color:#f92672">-</span> <span style="color:#ae81ff">1</span>);
}
</code></pre></div><ul>
<li>快速排序</li>
</ul>
<p>在区间中随机挑选一个元素作基准，将小于基准的元素放在基准之前，大于基准的元素放在基准之后，再分别对小数区与大数区进行排序。</p>
<p><em><strong>迭代法</strong></em></p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-c" data-lang="c"><span style="color:#66d9ef">typedef</span> <span style="color:#66d9ef">struct</span> _Range {
    <span style="color:#66d9ef">int</span> start, end;
} Range;
Range <span style="color:#a6e22e">new_Range</span>(<span style="color:#66d9ef">int</span> s, <span style="color:#66d9ef">int</span> e) {
    Range r;
    r.start <span style="color:#f92672">=</span> s;
    r.end <span style="color:#f92672">=</span> e;
    <span style="color:#66d9ef">return</span> r;
}
<span style="color:#66d9ef">void</span> <span style="color:#a6e22e">swap</span>(<span style="color:#66d9ef">int</span> <span style="color:#f92672">*</span>x, <span style="color:#66d9ef">int</span> <span style="color:#f92672">*</span>y) {
    <span style="color:#66d9ef">int</span> t <span style="color:#f92672">=</span> <span style="color:#f92672">*</span>x;
    <span style="color:#f92672">*</span>x <span style="color:#f92672">=</span> <span style="color:#f92672">*</span>y;
    <span style="color:#f92672">*</span>y <span style="color:#f92672">=</span> t;
}
<span style="color:#66d9ef">void</span> <span style="color:#a6e22e">quick_sort</span>(<span style="color:#66d9ef">int</span> arr[], <span style="color:#66d9ef">const</span> <span style="color:#66d9ef">int</span> len) {
    <span style="color:#66d9ef">if</span> (len <span style="color:#f92672">&lt;=</span> <span style="color:#ae81ff">0</span>)
        <span style="color:#66d9ef">return</span>; <span style="color:#75715e">// 避免len等於負值時引發段錯誤（Segment Fault）
</span><span style="color:#75715e"></span>    <span style="color:#75715e">// r[]模擬列表,p為數量,r[p++]為push,r[--p]為pop且取得元素
</span><span style="color:#75715e"></span>    Range r[len];
    <span style="color:#66d9ef">int</span> p <span style="color:#f92672">=</span> <span style="color:#ae81ff">0</span>;
    r[p<span style="color:#f92672">++</span>] <span style="color:#f92672">=</span> new_Range(<span style="color:#ae81ff">0</span>, len <span style="color:#f92672">-</span> <span style="color:#ae81ff">1</span>);
    <span style="color:#66d9ef">while</span> (p) {
        Range range <span style="color:#f92672">=</span> r[<span style="color:#f92672">--</span>p];
        <span style="color:#66d9ef">if</span> (range.start <span style="color:#f92672">&gt;=</span> range.end)
            <span style="color:#66d9ef">continue</span>;
        <span style="color:#66d9ef">int</span> mid <span style="color:#f92672">=</span> arr[(range.start <span style="color:#f92672">+</span> range.end) <span style="color:#f92672">/</span> <span style="color:#ae81ff">2</span>]; <span style="color:#75715e">// 選取中間點為基準點
</span><span style="color:#75715e"></span>        <span style="color:#66d9ef">int</span> left <span style="color:#f92672">=</span> range.start, right <span style="color:#f92672">=</span> range.end;
        <span style="color:#66d9ef">do</span>
        {
            <span style="color:#66d9ef">while</span> (arr[left] <span style="color:#f92672">&lt;</span> mid) <span style="color:#f92672">++</span>left;   <span style="color:#75715e">// 檢測基準點左側是否符合要求
</span><span style="color:#75715e"></span>            <span style="color:#66d9ef">while</span> (arr[right] <span style="color:#f92672">&gt;</span> mid) <span style="color:#f92672">--</span>right; <span style="color:#75715e">//檢測基準點右側是否符合要求
</span><span style="color:#75715e"></span> 
            <span style="color:#66d9ef">if</span> (left <span style="color:#f92672">&lt;=</span> right)
            {
                swap(<span style="color:#f92672">&amp;</span>arr[left],<span style="color:#f92672">&amp;</span>arr[right]);
                left<span style="color:#f92672">++</span>;right<span style="color:#f92672">--</span>;               <span style="color:#75715e">// 移動指針以繼續
</span><span style="color:#75715e"></span>            }
        } <span style="color:#66d9ef">while</span> (left <span style="color:#f92672">&lt;=</span> right);
 
        <span style="color:#66d9ef">if</span> (range.start <span style="color:#f92672">&lt;</span> right) r[p<span style="color:#f92672">++</span>] <span style="color:#f92672">=</span> new_Range(range.start, right);
        <span style="color:#66d9ef">if</span> (range.end <span style="color:#f92672">&gt;</span> left) r[p<span style="color:#f92672">++</span>] <span style="color:#f92672">=</span> new_Range(left, range.end);
    }
}
</code></pre></div><p><em><strong>递归法</strong></em></p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-c" data-lang="c"><span style="color:#66d9ef">void</span> <span style="color:#a6e22e">swap</span>(<span style="color:#66d9ef">int</span> <span style="color:#f92672">*</span>x, <span style="color:#66d9ef">int</span> <span style="color:#f92672">*</span>y) {
    <span style="color:#66d9ef">int</span> t <span style="color:#f92672">=</span> <span style="color:#f92672">*</span>x;
    <span style="color:#f92672">*</span>x <span style="color:#f92672">=</span> <span style="color:#f92672">*</span>y;
    <span style="color:#f92672">*</span>y <span style="color:#f92672">=</span> t;
}
<span style="color:#66d9ef">void</span> <span style="color:#a6e22e">quick_sort_recursive</span>(<span style="color:#66d9ef">int</span> arr[], <span style="color:#66d9ef">int</span> start, <span style="color:#66d9ef">int</span> end) {
    <span style="color:#66d9ef">if</span> (start <span style="color:#f92672">&gt;=</span> end)
        <span style="color:#66d9ef">return</span>;
    <span style="color:#66d9ef">int</span> mid <span style="color:#f92672">=</span> arr[end];
    <span style="color:#66d9ef">int</span> left <span style="color:#f92672">=</span> start, right <span style="color:#f92672">=</span> end <span style="color:#f92672">-</span> <span style="color:#ae81ff">1</span>;
    <span style="color:#66d9ef">while</span> (left <span style="color:#f92672">&lt;</span> right) {
        <span style="color:#66d9ef">while</span> (arr[left] <span style="color:#f92672">&lt;</span> mid <span style="color:#f92672">&amp;&amp;</span> left <span style="color:#f92672">&lt;</span> right)
            left<span style="color:#f92672">++</span>;
        <span style="color:#66d9ef">while</span> (arr[right] <span style="color:#f92672">&gt;=</span> mid <span style="color:#f92672">&amp;&amp;</span> left <span style="color:#f92672">&lt;</span> right)
            right<span style="color:#f92672">--</span>;
        swap(<span style="color:#f92672">&amp;</span>arr[left], <span style="color:#f92672">&amp;</span>arr[right]);
    }
    <span style="color:#66d9ef">if</span> (arr[left] <span style="color:#f92672">&gt;=</span> arr[end])
        swap(<span style="color:#f92672">&amp;</span>arr[left], <span style="color:#f92672">&amp;</span>arr[end]);
    <span style="color:#66d9ef">else</span>
        left<span style="color:#f92672">++</span>;
    <span style="color:#66d9ef">if</span> (left)
        quick_sort_recursive(arr, start, left <span style="color:#f92672">-</span> <span style="color:#ae81ff">1</span>);
    quick_sort_recursive(arr, left <span style="color:#f92672">+</span> <span style="color:#ae81ff">1</span>, end);
}
<span style="color:#66d9ef">void</span> <span style="color:#a6e22e">quick_sort</span>(<span style="color:#66d9ef">int</span> arr[], <span style="color:#66d9ef">int</span> len) {
    quick_sort_recursive(arr, <span style="color:#ae81ff">0</span>, len <span style="color:#f92672">-</span> <span style="color:#ae81ff">1</span>);
}
</code></pre></div><p>学习内容来自 <a href="https://www.runoob.com/cprogramming/c-tutorial.html">菜鸟教程</a></p></article>
    </section>

    <footer class="ui attached segment dream-tags">
      
        
          <a class="ui label" href="/tags/c" title="C">C</a>
        
      
      <div
        class="ui label"
        style="float: right; background: #1b1c1d !important; cursor: pointer;"
        onclick="savePostAsImg()">
        <i class="save icon"></i> Save as image
      </div>
    </footer>

    

    

  </div>
  <div class="sixteen wide mobile sixteen wide tablet four wide computer column">
    <article class="dream-header">
  <section class="ui top attached center aligned segment">
    <div class="ui small circular image">
      
        <img src="/img/psb25.jpg">
      
    </div>

    <h3 class="ui header">zhitaoZ&#39;s blog<div class="sub header" style="margin-top: 0.5rem;">No one is a island</div>
    </h3>

    <div class="ui horizontal list">
      
      <a class="item" href="/tags">
        <i class="tags icon" title="All Tags"></i>
      </a>
      <a class="item" href="/categories">
        <i class="th list icon" title="All Categories"></i>
      </a>
    </div>
  </section>

  
  <section class="ui attached center aligned segment dream-tags">
    
      <a class="ui label" href="/tags/c" title="c">c</a>
    
      <a class="ui label" href="/tags/git" title="git">git</a>
    
      <a class="ui label" href="/tags/markdown" title="markdown">markdown</a>
    
      <a class="ui label" href="/tags/%E7%BD%91%E7%AB%99" title="网站">网站</a>
    
  </section>
  

  
  <section class="ui attached segment dream-categories">
    <div class="ui accordion">
      
        <div class="title">
          <i class="dropdown icon"></i>
          <a href="/categories/%E8%87%AA%E5%AD%A6" class="item">自学</a>
        </div>
        <div class="content">
          <div class="ui list">
          
            <div class="item">
              <div class="content">
                <a href="https://zhitaoz.github.io/post/learnmd/" class="item">Markdown 基础语法</a>
              </div>
            </div>
          
            <div class="item">
              <div class="content">
                <a href="https://zhitaoz.github.io/post/learngit3/" class="item">Git 尝试pull request&amp; 接收pull request</a>
              </div>
            </div>
          
            <div class="item">
              <div class="content">
                <a href="https://zhitaoz.github.io/post/learngit2/" class="item">Git分支及远程相关操作</a>
              </div>
            </div>
          
            <div class="item">
              <div class="content">
                <a href="https://zhitaoz.github.io/post/learngit1/" class="item">Git基本操作</a>
              </div>
            </div>
          
            <div class="item">
              <div class="content">
                <a href="https://zhitaoz.github.io/post/learnc5/" class="item">C语言基础知识(五)</a>
              </div>
            </div>
          
            <div class="item">
              <div class="content">
                <a href="https://zhitaoz.github.io/post/learnc4/" class="item">C语言基础知识(四)</a>
              </div>
            </div>
          
            <div class="item">
              <div class="content">
                <a href="https://zhitaoz.github.io/post/learnc3/" class="item">C语言基础知识(三)</a>
              </div>
            </div>
          
            <div class="item">
              <div class="content">
                <a href="https://zhitaoz.github.io/post/learnc2/" class="item">C语言基础知识(二)</a>
              </div>
            </div>
          
            <div class="item">
              <div class="content">
                <a href="https://zhitaoz.github.io/post/learnc1/" class="item">C语言基础知识(一)</a>
              </div>
            </div>
          
            <div class="item">
              <div class="content">
                <a href="https://zhitaoz.github.io/post/bblog/" class="item">hugo搭建博客步骤(windows)</a>
              </div>
            </div>
          
          </div>
        </div>
      
    </div>
  </section>
  

  <section class="ui bottom attached center aligned segment">
      
      <p>© 2020 zhitaoZ&#39;s blog</p>
      
      <p>Powered by <a href="https://gohugo.io/" target="_blank">Hugo</a> with theme <a href="https://github.com/g1eny0ung/hugo-theme-dream" target="_blank">Dream</a>.</p>
  </section>
</article>

  </div>
</div>

        </section>
        <section class="back">
          
<nav class="ui secondary inverted menu dream-menu">

  <div class="item">
    <i class="large link bullseye icon dream-flip-toggle" title="Flip it!"></i>
  </div>
  <div class="item">
    <i class="large link home icon" title="Home" onclick="window.location.href = 'https:\/\/zhitaoz.github.io\/'"></i>
  </div>
  <div class="item">
    <i id="theme-switch" class="large link icon" onclick="themeSwitch()"></i>
  </div>
</nav>

          <div class="ui centered relaxed grid dream-grid dream-back">
  

  <section class="sixteen wide mobile eight wide tablet four wide computer column dream-column">
    <article>
      <div class="ui top attached segment">
        <h3 class="ui header">Social Links</h3>
      </div>
      <div class="ui attached segment">
        <nav class="ui secondary menu dream-menu">
          
            <div class="item">
              <a href="mailto:zhangzhitao@bupt.edu.cn">
                <i class="large mail icon" title="email"></i>
              </a>
            </div>
          

          
            <div class="item">
              <a href="https://github.com/zhitaoZ" target="_blank">
                <i class="large github icon" title="github"></i>
              </a>
            </div>
          

          

          

          
        </nav>
      </div>
    </article>
  </section>

  <section class="sixteen wide mobile eight wide tablet four wide computer column dream-column">
    
  </section>

  
  

</div>

        </section>
      </div>
    </div>

    <script src="/js/jquery.min.js"></script>
<script src="/js/semantic.min.js"></script>
<script src="/js/imagesloaded.pkgd.min.js"></script>
<script src="/js/masonry.pkgd.min.js"></script>
<script src="/js/nav.js"></script>
<script src="/js/header.js"></script>
<script src="/js/main.js"></script>
<script src="/js/theme.js"></script>
<script src="/js/html2canvas.min.js"></script>



  </body>
</html>
